class Solution:

    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        lis =  []
        cur = head
        while cur is not None:
            lis.append(cur.val)
            cur = cur.next
        return lis == lis[::-1]

    '''   复杂度分析
        时间复杂度：O(n)，其中n
        指的是链表的大小。
        空间复杂度：O(n)，其中
        n指的是链表的大小。'''

    def isPalindrome2(self, head: Optional[ListNode]) -> bool:

        if head is None:
            return True

            # 找到前半部分链表的尾节点并反转后半部分链表
        first_half_end = self.end_of_first_half(head)
        second_half_start = self.reverse_list(first_half_end.next)

        # 判断是否回文
        result = True
        first_position = head
        second_position = second_half_start
        while result and second_position is not None:
            if first_position.val != second_position.val:
                result = False
            first_position = first_position.next
            second_position = second_position.next

            # 还原链表并返回结果
        first_half_end.next = self.reverse_list(second_half_start)
        return result

    '''    复杂度分析
        时间复杂度：O(n)，其中n
        指的是链表的大小。
        空间复杂度：O(1)。我们只会修改原本链表中节点的指向，而在堆栈上的堆栈帧不超过   O(1)'''

    def end_of_first_half(self, head):
        fast = head
        slow = head
        while fast.next is not None and fast.next.next is not None:
            fast = fast.next.next
            slow = slow.next
        return slow

    def reverse_list(self, head):
        previous = None
        current = head
        while current is not None:
            next_node = current.next
            current.next = previous
            previous = current
            current = next_node
        return previous



